A linked list is simply a chain of structures which contain a pointer to the next element. That is about the simplest explanation I can provide. It is one of the simpler of the advanced data structures, and is frequently one of the first things a student learns in a second year university level data structures course. Here is a diagram to illustrate what I mean:
This definition applies only to Singly Linked Lists - Doubly Linked Lists, Skip Lists and Circle Lists are different.
Some common examples of a linked list:
And the list goes on ...
- The AmigaDOS Viewport structure always points to the next viewport. You can have multiple viewports in the same list
- Hash tables use linked lists for collission resolution
- Any "File Requester" dialog uses a linked list
- Binary Trees
- Stacks and Queues can be implemented with a doubly linked list
- Relational Databases (EG Microsoft Access)
How to address elements in a linked list
It is always a good idea to put your linked list into it's own Class. This makes it much easier to manage as you can write your own methods to manipulate it. A linked list class should contain the following elementary functions:
Other functions such as search, sort, and a remove from within the list are also useful, and implementation of these will be provided in pseudo-code and in C++ in the sample source code.
- Add To Head (Var_Type element)
- Add To Tail (Var_Type element)
- Var_Type Remove From Head
- Var_Type Remove From Tail
A list item has a pointer to the next element, or to 0 if the current element is the tail (end of the list). This pointer is of the same type as the structure itself. This structure that contains elements and pointers to the next structure is called a Node. A sample call would look like the following:
//move to the next element in the list temp = temp->next; //move 2 elements down the list temp = temp->next->next; // and so on //go to the head of the list temp = head; // temp = tail to go to the end
These 3 examples show how easy it is to traverse a list. As you move though the list, to access the elements all you need to do is address the appropriate feild in the Node structure.
value = Node->info; // info is the data contained at this location in the list
Elementary Linked List Functions
I have created a set of elementary function that should be included in all linked lists. These functions allow the user to add or remove elements to the linked list. In this example, the datatype I am going to use is undefined. Depending on the language you wish to use for actual implemenation, you can use virtually any datatype (even a linked list itself!)
Adding an element to the head of a linked list
Adding an element to the head of a linked list is quite simple. First the procedure must allocate the appropriate resources/memory in such a way that it will point to the head of the list. Then it will make sure that current element (head+1 if you will) is not the last element in the list. If so, it will change the pointers accordingly.
// Add an element to the start of the linked list procedure AddToHead(element) head = new Node(element, head) if(not the Tail) tail = head end if end procedure
Adding an element to the tail of a linked list
Adding an element to the tail of a list is slightly different. The procedure must allocate a node that is pointed to by the last element in the list. Then the procedure must set the current node pointer to the next element, and do the same for the tail pointer (tail+1 if you will).
// Add an element to the tail of the linked list procedure AddToTail(element) if(this is the Tail) tail->next = new Node(el) tail = tail->next endif else head = tail = new Node(el) end procedure
Removing an element from the head of a linked list
This one is a little harder to follow. First, it must get the element contained in head. Then it must patch up the linked list accordingly. The bond between head and the next element is broken, so the next element in the list is set to be the head.
// Remove an element from the head of the linked list procedure RemoveFromHead():integer if(this is the Head) element = head->info temp = head if(this is the last item in the list) Break pointer connection between head and tail to terminate list else set head.next to equal next item in list end if release temp from from memory pool return element else return 0 end if end procedure
Removing an element from the head of a linked list
Removing an element from the tail of the list is a bit simpler. First, the element must be obtained, then the memory used by the tail node is released. The tail pointer is set at the preceeding element and the procedure makes sure that this is not the last element in the list.
// Remove an element from the tail of the linked list procedure RemoveFromTail():integer if(this is the Tail) element = tail->info if(this is the last item in the list) Break pointer connection between head and tail to terminate list release head from memory pool else Traverse list until you reach the tail release tail from memory pool set tail pointer to previous element if one exists set tail's pointer to next element to null end if return element else return 0 end if end procedure
Conclusion
Singly linked lists are useful data structures, especially if you need to automatically allocate and de-allocate space in a list. The code and complexity of these algorithms is bigger, but the tradeoff is ease of use. As far as complexity is concerned, a linked list should never exceed O(n2). If you are very lucky, linear time can be acheived (only under several conditions, such as there being only 1 item in the list, or the current element pointed at is the head or the tail). Sorting linked lists can be a chore, but with careful selection of sorting algorithms, nearly constant time can be acheived. Counting Sort works the best for integers, and Quicksort works great for non-integer items (such as floats).
Download Linked List Class
This list class is written in C++. It has been tested with Storm C++ and Microsoft Visual C++ 4.1. It worked fine with both.
Download linklist.cppBack to index